package 数组.下一个更大元素2;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/2/17 17:18
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[] array = {5,4,3,2,1};
        int[] ints = nextGreaterElements2(array);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }

    //快慢指针
    public static int[] nextGreaterElements(int[] nums) {
        int[] result = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            int fastIndex = i+1;
            if (i == nums.length-1){
                fastIndex = 0;
            }
            int countNum = nums.length;
            while (countNum > 0){
                if (fastIndex == nums.length){
                    fastIndex = 0;
                }
                if (nums[fastIndex] > nums[i]){
                    result[i] = nums[fastIndex];
                    break;
                }
                countNum--;
                fastIndex++;
            }
            if (countNum == 0){
                result[i] = -1;
            }
        }
        return result;
    }

    /**
     * 通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了
     * @param nums
     * @return
     */
    //单调栈
    public static int[] nextGreaterElements2(int[] nums) {
        int[] ans = new int[nums.length];
        Arrays.fill(ans, -1);   //初始化，将数组所有元素全部初始化为-1
        //栈中存放的是数组的下标
        Deque<Integer> stack = new LinkedList<>();
        //循环数组，扩大遍历的边界条件，大于数组长度的时候取余
        for (int i = 0; i < 2 * nums.length - 1; i++) {
            int j = i % nums.length;
            ////下标j每次会走在栈的前面一个和栈顶内容进行比较
            while (!stack.isEmpty() && nums[j] > nums[stack.peek()]) {
                int index = stack.pop();
                ans[index] = nums[j];
            }
            //单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取
            stack.push(j);
        }
        return ans;
    }


}
